package linkedtable;



/**
 * @Description 206. 反转链表
 * @Author Firenut
 * @Date 2023-01-15 20:56
 */
public class T206_reverseList {

    //法1: 三指针 迭代
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode pre, cur, next;
        pre = null;
        cur = head;
        next = cur.next;
        while (next != null) {
            cur.next = pre;
            pre = cur;
            cur = next;
            next = next.next;
        }
        cur.next = pre;
        return cur;
    }

    //法2: 递归
    public ListNode reverseList2(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode p = head;
        while (p.next != null) { //需要提前保留尾部结点的指针
            p = p.next;
        }

        ListNode node = dfs(head);
        node.next = null;
        return p;
    }
    public ListNode dfs(ListNode node) {
        if (node.next == null) {
            return node;
        }
        ListNode next = dfs(node.next);
        next.next = node;
        return node;
    }

    //法3:
    public ListNode reverseList3(ListNode head) {
        return dfs(head, null);
    }

    public ListNode dfs(ListNode cur, ListNode pre) {
        if (cur == null) {
            return pre;
        }
        ListNode head = dfs(cur.next, cur);
        cur.next = pre;
        return head;
    }

}

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
